/*
 * @lc app=leetcode.cn id=827 lang=typescript
 *
 * [827] 最大人工岛
 */

// @lc code=start

class Union {
  data: number[];
  size: number[];
  constructor(n: number) {
    this.data = new Array(n).fill(-1).map((_, idx) => idx);
    this.size = new Array(n).fill(1);
  }
  union(x: number, y: number): void {
    let rx = this.find(x);
    let ry = this.find(y);
    if (rx === ry) return;
    if (this.size[rx] > this.size[ry]) {
      [rx, ry] = [ry, rx];
    }
    this.size[ry] += this.size[rx];
    this.data[rx] = ry;
  }
  find(x: number): number {
    if (this.data[x] !== x) this.data[x] = this.find(this.data[x]);
    return this.data[x];
  }
}

function largestIsland(grid: number[][]): number {
  const n = grid.length;
  const dirs = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  // 从下标1开始计算，所以数组长度加1
  const unions = new Union(n * n + 1);
  // 遍历每个点，相邻的1做连通连接
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 0) continue;
      for (const [x, y] of dirs) {
        const nx = i + x;
        const ny = j + y;
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue;
        // 二维坐标转一维坐标，从1开始计数
        unions.union(i * n + j + 1, nx * n + ny + 1);
      }
    }
  }

  // 遍历每个值为0的点，尝试反转后计算连通岛屿的面积
  let ans = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        const root = unions.find(i * n + j + 1);
        ans = Math.max(ans, unions.size[root]);
      } else {
        let total = 1;
        // 记录四边扩展的时候是否有重复岛屿
        const set = new Set<number>();
        for (const [x, y] of dirs) {
          let nx = i + x;
          let ny = j + y;
          // 四边扩展时是否越界或者相邻点不是岛屿
          if (nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] === 0) continue;
          const root = unions.find(nx * n + ny + 1);
          if (set.has(root)) continue;
          total += unions.size[root];
          set.add(root);
        }
        ans = Math.max(ans, total);
      }
    }
  }
  return ans;
}
// @lc code=end
